def binary_search_recursive(arr, target, left, right):
    """
    递归版二分查找：通过递归缩小查找范围
    arr：有序数组
    target：待查找元素
    left/right：当前查找区间的左右边界
    """
    if left > right:
        return -1
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)

# 测试
arr = [1, 2, 3, 4, 5, 6, 9]
print(binary_search_recursive(arr, 5, 0, len(arr)-1))  # 输出：4